#include "headfiles.h"

using namespace std;

bool calcMaxSubmatrix(int *s, int m, int n, POINT *start, POINT *end) {
    if (s == NULL ||
        m < 1 ||
        n < 1 ||
        start == NULL ||
        end == NULL) {
        cout << "Invalid input arguments!" << endl;
        return false;
    }

    int max_sum = s[0];
    int sum;
    int start_x, start_y, end_x, end_y;

    int i, j;
    for (end_x = 0; end_x < m; end_x++) {
        for (end_y = 0; end_y < n; end_y++) {
            for (start_x = 0; start_x <= end_x; start_x++) {
                for (start_y = 0; start_y <= end_y; start_y++) {
                    sum = 0;
                    for (i = start_x; i <= end_x; i++) {
                        for (j = start_y; j <= end_y; j++) {
                            int index = i * n + j;
                            sum += s[index];
                        }
                    }

                    if (max_sum < sum) {
                        max_sum = sum;
                        start->x = start_x;
                        start->y = start_y;
                        end->x = end_x;
                        end->y = end_y;
                    }
                }
            }
        }
    }

    return true;
}

bool calcMaxSubmatrix1(int *s, int m, int n, POINT *start, POINT *end) {
    if (s == NULL ||
        m < 1 ||
        n < 1 ||
        start == NULL ||
        end == NULL) {
        cout << "Invalid input arguments!" << endl;
        return false;
    }

    int max_sum = s[0];
    int sum, submatrix_sum;
    int start_x, start_y, end_x, end_y;

    int i, j, index;
    int *column_sum = (int *)malloc(sizeof(int) * n);
    if (column_sum == NULL) {
        cout << "Allocate column_sum buffer error!" << endl;
        return false;
    }
    int row_sum;

    for (end_x = 0; end_x < m; end_x++) {
        for (end_y = 0; end_y < n; end_y++) {
            // calculate the sum of each column from row 0 to row end_x
            memset(column_sum, 0, sizeof(int) * n);
            submatrix_sum = 0;
            for (j = 0; j <= end_y; j++) {
                for (i = 0; i <= end_x; i++) {
                    index = i * n + j;
                    column_sum[j] += s[index];
                }
                submatrix_sum += column_sum[j];
            }

            for (start_x = 0; start_x <= end_x; start_x++) {
                sum = submatrix_sum;
                start_y = 0;
                do {
                    if (max_sum < sum) {
                        start->x = start_x;
                        start->y = start_y;
                        end->x = end_x;
                        end->y = end_y;
                        max_sum = sum;
                    }
                    sum -= column_sum[start_y];
                    start_y++;
                }
                while (start_y <= end_y);

                // after processing each row, remove the element from the
                // column_sum array
                row_sum = 0;
                for (j = 0; j <= end_y; j++) {
                    index = start_x * n + j;
                    column_sum[j] -= s[index];
                    row_sum += s[index];
                }
                submatrix_sum -= row_sum;
            }
        }
    }

    return true;
}

